package kmp;


import java.util.HashMap;

/**
 * 三种解法
 *
 * 暴力搜索  BF
 * 滚动哈希  RK
 *          KMP
 */
public class 实现strStr_28 {
    public static void main(String[] args) {
        实现strStr_28 a = new 实现strStr_28();
        int i = a.strStr_rk("baabbaaaaaaabbaaaaabbabbababaabbabbbbbabbabbbbbbabababaabbbbbaaabbbbabaababababbbaabbbbaaabbaababbbaabaabbabbaaaabababaaabbabbababbabbaaabbbbabbbbabbabbaabbbaa",
                "bbaaaababa");
        System.out.println();
    }

    /**
     * 滚动哈希  按照滑动窗口来理解 看是不是要的窗口  用hash来求合适
     */
    public int strStr_rk(String haystack, String needle) {
        char[] str = haystack.toCharArray();
        char[] pattern = needle.toCharArray();
        if (pattern.length == 0) {
            return 0;
        }
        if (str.length == 0) {
            return -1;
        }
        double hashFactor =  101/*Math.pow(101, pattern.length - 1)*/;
        // 求pattern的hash值  用自定义求法
        double  hashTarget = hash(pattern, hashFactor);
        // 求str头部 pattern长度的hash值
        double strInitHash = hash(haystack.substring(0, pattern.length).toCharArray(), hashFactor);

        if(hashTarget == strInitHash && isEqual(str, pattern, 0)) return 0;
        for (int i = pattern.length  ; i < str.length; i ++) {
            // 求当前窗口hash值
            strInitHash = strInitHash + str[i] * hashFactor - str[i - pattern.length] * hashFactor;
            //

            //  isEqual  防止  hash(pi) == hash(ip) 顺序不同值相同的情况
            if(strInitHash == hashTarget  && isEqual(str, pattern, i - pattern.length + 1)) {
                // 与strStr_kmp  i - pattern.length + 1 对比看
                return i - pattern.length + 1;
            }
        }

        return -1;
    }

    private boolean isEqual(char[] str, char[] pattern, int i) {
        int j = 0;
        while(j < pattern.length && str[i] == pattern[j]) {
            i ++;
            j ++;
        }
        if(j == pattern.length) return true;
        return false;
    }


    /**
     * 暴力搜索  逐个匹配
     */
    public int strStr_bf(String haystack, String needle) {
        char[] str = haystack.toCharArray();
        char[] pattern = needle.toCharArray();
        if (pattern.length == 0) {
            return 0;
        }
        if (str.length == 0) {
            return -1;
        }
        for (int i = 0, pi = 0; i < str.length;) {
            // 若相等 判断后续
            // 若不等   看pattern[0]  并移动到至少一个相等
            if(pattern[pi] == str[i]) {
                pi ++;
                i ++;
            } else {
                // str回退 到起始点的下一位置 重新逐个比较
                i = i - pi + 1;
                pi = 0;
            }
            //

            //  pi 从0 ++ 了pattern.length 次  最后多加了一次  刚好是起始位置
            if(pi == pattern.length ) {
                // 与strStr_kmp  i - pattern.length + 1 对比看
                return i - pi;
            }
        }

        return -1;
    }

    public int strStr_kmp(String haystack, String needle) {
        char[] str = haystack.toCharArray();
        char[] pattern = needle.toCharArray();
        if (pattern.length == 0) {
            return 0;
        }
        if (str.length == 0) {
            return -1;
        }

        return kmp(str, pattern);
    }

    private int kmp(char[] str, char[] pattern) {
        int[] nextIdx = getNextIdx(pattern);
        int patternCur = 0;
        for (int i = 0; i < str.length; i++) {
            //  和求nextIdx数组逻辑相同（看做后缀字符串和前缀字符串两个子串的匹配）  两个不同字符串的匹配  
            //   patternCur == 0 的时候表示从patter第一个字符开始匹配
            //  当patternCur > 0 的时候表示有一部分匹配上了 见底下 patternCur ++;代码  
            //                          当 只匹配上了前面部分 最后一个没匹配上的时候  
            //                              如 str  dababac  匹配 pattern abac  到了 abab  和abac 匹配时 b != c   i = 4  j = 3
            //                              这时转而看str  的  str[4] 的 b  和 pattern[nextIdx[3 - 1] = 1] 的 b是否匹配  匹配了就继续往后找
            //                              这就是next数组的下一匹配位置的含义 ：  相同前后缀的长度   abab    2 
            //                            next一直回退 一直回退到pattern[0]
            while (patternCur > 0 && pattern[patternCur] != str[i]) {
                patternCur = nextIdx[patternCur - 1];
            }
            //  有相同的字符  等着匹配下一个字符
            if (pattern[patternCur] == str[i]) {
                patternCur++;
            }
            //  patternCur ++ 了 pattern.length次  表示找到了完全相等的部分
            if (patternCur == pattern.length) {
                return i - pattern.length + 1;
            }
        }

        return -1;
    }

    /**
     * 计算next数组
     * 版本2
     * 找next[] 数组也是一次kmp  就是用已知的next[i - 1]  求未知的next[i]
     */
    private int[] getNextIdx(char[] pattern) {
        int[] nextIdx = new int[pattern.length];
        int cur = 0;
        for (int i = 1; i < pattern.length; i++) {
            // 与自己写的代码版本1的区别
            // 重点是这里的回溯思想  并非是从头直接开始
            // 如 abacdabab  当 i = 8  k  = 3 时  
            // 1. 虽然  前缀abac 不能匹配上  后缀abab  
            //    但是前后缀ab还是相同的   不能直接置为0  
            // 2. 思路转化为 找abac的头部 有没有和  abab  的尾部有没有相同的串看子串
            //        转化为 parrern[ cur - 1 ]  即 aba 有没有相等前后缀   等价于 nextIdx[cur - 1]
            // 此时缩小到 k = next[2] = 1  即k = 1  用 前缀aba 的b匹配 i = 8 即后缀bab 第二个b  匹配成功   k ++
            //  回溯  找前后缀相等的最小cur值
            // cur > 0   因为只有1个的时候不用找  cur 就是0
            while (cur > 0 && pattern[cur] != pattern[i]) {
                cur = nextIdx[cur - 1];
            }
            if (pattern[cur] == pattern[i]) {
                cur++;
            }
            nextIdx[i] = cur;
        }
        return nextIdx;
    }

    /**
     * 计算next数组
     * 版本1  这种方式有问题
     * next[i] = x；表示needle[0,i]的最长相同前后缀长度为x；
     * 例如 needle = aabaa, 其对应next数组为：0，1，0，1，2；
     */
    public int[] next_1(char[] needle, int len) {
        int[] next = new int[needle.length];
        int l = 0;

        // 双指针 后面指针开始循环
        for (int r = 1; r < needle.length; r++) {
            if (needle[l] == needle[r]) {
                l++;
                next[r] = l;
            } else {
                l = 0;
                next[r] = l;
            }
        }
        return next;
    }



    private double hash(char[] charArray, double hashFactor) {
        double hash = 0;
        for(int i = 0 ; i< charArray.length; i++) {

            hash += charArray[i]* hashFactor;
        }
        return hash;
    }
}
